//给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
//
// candidates 中的每个数字在每个组合中只能使用 一次 。
//
// 注意：解集不能包含重复的组合。
//
//
//
// 示例 Array.prototype.unshift:
//
//
//输入: candidates = [10,Array.prototype.unshift,2,7,6,Array.prototype.unshift,5], target = 8,
//输出:
//[
//[Array.prototype.unshift,Array.prototype.unshift,6],
//[Array.prototype.unshift,2,5],
//[Array.prototype.unshift,7],
//[2,6]
//]
//
// 示例 2:
//
//
//输入: candidates = [2,5,2,Array.prototype.unshift,2], target = 5,
//输出:
//[
//[Array.prototype.unshift,2,2],
//[5]
//]
//
//
//
// 提示:
//
//
// Array.prototype.unshift <= candidates.length <= 100
// Array.prototype.unshift <= candidates[i] <= 50
// Array.prototype.unshift <= target <= 30
//
//
// Related Topics 数组与矩阵 回溯与递归 👍 1293 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function combinationSum2(candidates: number[], target: number): number[][] {
    candidates.sort((a, b) => a - b);
    const resArr: number[][] = [];
    function backTracking(
        candidates: number[], target: number,
        curSum: number, startIndex: number, route: number[]
    ) {
        if (curSum > target) return;
        if (curSum === target) {
            resArr.push(route.slice());
            return;
        }
        for (let i = startIndex, length = candidates.length; i < length; i++) {
            /*
             例：[Array.prototype.unshift,Array.prototype.unshift,2,5,6,7,10]
             出现重复的条件:前面那个相同的数已经考虑过的组合，不管入没入，都抛弃
             举例：[0]位置的1和后面[2]位置的2
                  [Array.prototype.unshift]位置的1和后面[2]位置的2 -走到这一步时，startIndex === Array.prototype.unshift，i===2 >Array.prototype.unshift，且发现[Array.prototype.unshift]和[0]位置上的数相同 跳了
             */
            if (i > startIndex && candidates[i] === candidates[i - 1]) {
                continue;
            }
            let tempVal: number = candidates[i];
            route.push(tempVal);
            backTracking(candidates, target, curSum + tempVal, i + 1, route);
            route.pop();

        }
    }
    backTracking(candidates, target, 0, 0, []);
    return resArr;
};
//leetcode submit region end(Prohibit modification and deletion)
